package ml;

import java.util.ArrayList;

import util.DataUtil;

public class AdaBoostTrainer {
	public static StrongClassifer train(ArrayList<SampleData> samples, ArrayList<Boolean> labels,
					int cycles) {
		assert (samples.size() > 0);
		assert (samples.size() == labels.size());

		// 每一列是一种特征
		ArrayList<ArrayList<Double>> featuresBasedonFeature = getFeatureVols(samples);

		// 每一列是一个样本的所有特征
		ArrayList<ArrayList<Double>> featuresBasedonSample = DataUtil
						.Transpose(featuresBasedonFeature);

		return trainStrong(featuresBasedonFeature, labels, cycles, featuresBasedonSample);
	}

	/**
	 * training using features, called by train()
	 * 
	 * @param featuresBasedonFeature
	 *            每个feature一列，一列中包含了所有sample的这种特征的值
	 * @param labels
	 *            所有sample的label
	 * @param cycles
	 *            训练轮数
	 * @return 训练得到的强分类器
	 */
	protected static StrongClassifer trainStrong(
					ArrayList<ArrayList<Double>> featuresBasedonFeature, ArrayList<Boolean> labels,
					int cycles, ArrayList<ArrayList<Double>> featuresBasedonSample) {
		StrongClassifer strongClassifier = new StrongClassifer();

		int sampleNum = featuresBasedonFeature.get(0).size();
		double initWeight = 1.0 / sampleNum;
		ArrayList<Double> weightsOfSamples = new ArrayList<Double>(sampleNum);
		for (int i = 0; i < sampleNum; ++i) {
			weightsOfSamples.add(initWeight);
		}

		ArrayList<ArrayList<Integer>> sortFeatureIndices = getSortFeatureIndex(featuresBasedonFeature);

		for (int i = 0; i < cycles; ++i) {
			updateStrongClassifier(strongClassifier, weightsOfSamples, labels,
							featuresBasedonFeature, sortFeatureIndices, featuresBasedonSample);
		}

		return strongClassifier;
	}

	private static void updateStrongClassifier(StrongClassifer strongClaissifer,
					ArrayList<Double> weightsOfSamples, ArrayList<Boolean> labels,
					ArrayList<ArrayList<Double>> featureBasedonFeature,
					ArrayList<ArrayList<Integer>> sortFeatureIndices,
					ArrayList<ArrayList<Double>> featuresBasedonSample) {
		double minErrorRate = Double.MAX_VALUE;
		WeakClassifier bestWeakClassifier = null;
		int bestFeatureIndex = 0;

		ArrayList<Double> curFeatureVol = null;
		ArrayList<Integer> curSortFeatureIndex = null;
		for (int i = 0; i < featureBasedonFeature.size(); ++i) {
			WeakClassifier tmpWeakClassifer = new WeakClassifier();
			curFeatureVol = featureBasedonFeature.get(i);
			curSortFeatureIndex = sortFeatureIndices.get(i);
			double curErrorRate = trainWeakClassifer(tmpWeakClassifer, weightsOfSamples, labels,
							curFeatureVol, curSortFeatureIndex);
			if (curErrorRate < minErrorRate) {
				minErrorRate = curErrorRate;
				bestFeatureIndex = i;
				bestWeakClassifier = tmpWeakClassifer;
			}
		}

		// avoid divided by zero
		if (minErrorRate < MLConstants.MIN_TRAIN_ERROR_RATE) {
			minErrorRate = MLConstants.MIN_TRAIN_ERROR_RATE;
		}

		ArrayList<Boolean> weakClassifierEvaluateResult = evaluateWeakClassifier(
						bestWeakClassifier, featureBasedonFeature.get(bestFeatureIndex), labels);

		/*
		 * double errorNum = 0; for (Boolean element :
		 * weakClassifierEvaluateResult) { if (!element) { ++errorNum; } }
		 * System.out.println("Weighted minErrorRate: " + minErrorRate +
		 * "    Evaluate UnWeighted error rate: " + errorNum / labels.size());
		 */
		double alpha = 0.5 * Math.log((1 - minErrorRate) / minErrorRate);
		updateWeights(weightsOfSamples, weakClassifierEvaluateResult, alpha);
		strongClaissifer.addWeakClassifer(bestWeakClassifier, bestFeatureIndex, alpha);

		/*
		 * ArrayList<Boolean> strongClassifierEvaluateResult =
		 * evaluateStrongClassifier(strongClaissifer, featuresBasedonSample,
		 * labels);
		 * 
		 * errorNum = 0; for (Boolean element : strongClassifierEvaluateResult)
		 * { if (!element) { ++errorNum; } }
		 * System.out.println("Evaluate strong error rate: " + errorNum /
		 * labels.size() + "\n");
		 */
	}

	/**
	 * @param weakClassifer
	 * @param weightsOfSamples
	 * @param labels
	 * @param featureVol
	 * @param sortFeatureIndex
	 * @return errorRate of the newly trained weakClassifier
	 */
	private static double trainWeakClassifer(WeakClassifier weakClassifer,
					ArrayList<Double> weightsOfSamples, ArrayList<Boolean> labels,
					ArrayList<Double> featureVol, ArrayList<Integer> sortFeatureIndex) {
		assert (null != weakClassifer);

		double min_weights_sum = Double.MAX_VALUE;
		int min_weights_sum_index = 0;
		double max_weights_sum = Double.MIN_VALUE;
		int max_weights_sum_index = 0;
		double weights_sum = 0;
		for (Integer index : sortFeatureIndex) {
			if (labels.get(index)) {
				weights_sum += weightsOfSamples.get(index);
			} else {
				weights_sum -= weightsOfSamples.get(index);
			}

			if (weights_sum < min_weights_sum) {
				min_weights_sum_index = index;
				min_weights_sum = weights_sum;
			}
			if (weights_sum > max_weights_sum) {
				max_weights_sum_index = index;
				max_weights_sum = weights_sum;
			}
		}

		double error_rate_less_is_pos = 0.5 * (1 + weights_sum - 2 * max_weights_sum);
		double error_rate_less_is_neg = 0.5 * (1 - weights_sum + 2 * min_weights_sum);
		double min_error_rate = 0;

		if (error_rate_less_is_pos < error_rate_less_is_neg) {
			min_error_rate = error_rate_less_is_pos;
			weakClassifer.m_less_is_pos = true;
			weakClassifer.m_threshold = featureVol.get(max_weights_sum_index)
							+ MLConstants.THRESHOLD_BIAS;
		} else {
			min_error_rate = error_rate_less_is_neg;
			weakClassifer.m_less_is_pos = false;
			weakClassifer.m_threshold = featureVol.get(min_weights_sum_index)
							+ MLConstants.THRESHOLD_BIAS;
		}

		return min_error_rate;
	}

	private static ArrayList<Boolean> evaluateWeakClassifier(WeakClassifier weakClassifier,
					ArrayList<Double> features, ArrayList<Boolean> labels) {
		ArrayList<Boolean> result = new ArrayList<Boolean>(labels.size());

		for (int i = 0; i < labels.size(); ++i) {
			if (weakClassifier.judge(features.get(i))) {
				result.add(labels.get(i));
			} else {
				result.add(!labels.get(i));
			}
		}

		return result;
	}

	/*
	 * private static ArrayList<Boolean>
	 * evaluateStrongClassifier(StrongClassifer strongClassifier,
	 * ArrayList<ArrayList<Double>> features, ArrayList<Boolean> labels) {
	 * ArrayList<Boolean> result = new ArrayList<Boolean>(labels.size());
	 * 
	 * for (int i = 0; i < labels.size(); ++i) { if
	 * (strongClassifier.judge(features.get(i))) { result.add(labels.get(i)); }
	 * else { result.add(!labels.get(i)); } }
	 * 
	 * return result; }
	 */

	private static ArrayList<ArrayList<Double>> getFeatureVols(ArrayList<SampleData> samples) {
		ArrayList<ArrayList<Double>> featureVol = new ArrayList<ArrayList<Double>>();

		int featureVecSize = samples.get(0).get_feature().size();
		for (int i = 0; i < featureVecSize; ++i) {
			featureVol.add(new ArrayList<Double>(samples.size()));
		}

		for (SampleData aSample : samples) {
			for (int j = 0; j < aSample.get_feature().size(); ++j) {
				featureVol.get(j).add(aSample.get_feature().get(j));
			}
		}

		return featureVol;
	}

	private static ArrayList<ArrayList<Integer>> getSortFeatureIndex(
					ArrayList<ArrayList<Double>> featureVols) {
		ArrayList<ArrayList<Integer>> sortFeatureIndices = new ArrayList<ArrayList<Integer>>();

		for (ArrayList<Double> aFeatureVec : featureVols) {
			ArrayList<Integer> sortedIndices = util.ExtendSorter.getIndiceAfterSorting(aFeatureVec);
			sortFeatureIndices.add(sortedIndices);
		}

		return sortFeatureIndices;
	}

	private static void updateWeights(ArrayList<Double> weights,
					ArrayList<Boolean> weakClassiferEvaluateResult, double alpha) {
		double oldWeight = 0;
		for (int i = 0; i < weights.size(); ++i) {
			oldWeight = weights.get(i);
			if (weakClassiferEvaluateResult.get(i)) {
				weights.set(i, oldWeight * Math.exp(-alpha));
			} else {
				weights.set(i, oldWeight * Math.exp(alpha));
			}
		}

		normalizeWeights(weights);
	}

	private static void normalizeWeights(ArrayList<Double> weights) {
		double sum = 0;
		for (Double value : weights) {
			sum += value;
		}

		for (int i = 0; i < weights.size(); ++i) {
			weights.set(i, weights.get(i) / sum);
		}
	}
}
